package com.algorithm.dp;

public class Robber {
    // 状态转移方程为 f[i] = max{f[i-1],f[i-2] + v[i]}
    public static void main(String[] args) {
        int[] house = {1,2,3,1};
        int [] sum = new int[house.length ];
        for (int i = 0; i < sum.length; i++) {
            sum[i] =-1;
        }
        int maxSumValue = searchMaxSumValue(house, house.length-1, sum);
        int maxSumValue0 = searchMaxSumValue0(house, house.length-1, sum);
        System.out.println(maxSumValue);
        System.out.println(maxSumValue0);
        int rob = rob(new int[]{1, 2, 3, 1});
        System.out.println(rob);
    }

    public static int rob(int[] nums) {
        if(nums.length == 0){
            return 0;
        }else if(nums.length == 1){
            return nums[0];
        }
        int [] sum = new int[nums.length ];

        for (int i = 0; i < sum.length; i++) {
            sum[i] =-1;
        }
        int i = searchMaxSumValue0(nums, nums.length - 1, sum);
        return i;
    }

    /**
     *@author : daniel.yang
     *@date : 2018/11/6
     *@desc :递归实现
     */
    private static int searchMaxSumValue(int[] house, int nums, int[] sum) {
        if (nums < 0){
            return 0;
        }
        if (sum[nums] != -1){
            return sum[nums];
        }
        sum[nums] = Math.max(searchMaxSumValue(house,nums-1,sum), searchMaxSumValue(house,nums-2,sum) + house[nums]);
        return sum[nums];
    }

    /**
     *@author : daniel.yang
     *@date : 2018/11/6
     *@desc : 递推实现
     *@param house :
     *@param nums :
     *@param sum :
     */
    private static int searchMaxSumValue0(int[] house, int nums, int[] sum) {
        sum[0] = house[0];
        sum[1] = Math.max(house[0],house[1]);
        for (int i = 2; i <= nums; i++) {
            sum[i] = Math.max(sum[i-1],sum[i-2] + house[i]);
        }
        return sum[nums];
    }
}
